public class Test {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {0,2,3};
        int ret = s.takeAttendance(nums);
        System.out.println(ret);
    }
}

class Solution {
    //方法4：数学——高斯求和公式
    public int takeAttendance(int[] A) {
        int count = 0;
        for(int i = 0; i < A.length; i++){
            count += A[i];
        }
        int sum = (0+A[A.length-1])/2*A.length;
        return sum - count;
    }
    //方法3：位运算
    public int takeAttendance3(int[] A) {
        //
    }

    //方法2：直接遍历寻找结果
    public int takeAttendance2(int[] A) {
        int i = 0;
        for( i = 0; i < A.length; i++){
            if(A[i] != i){
                break;
            }
        }
        return i;
    }
    //方法5：二分算法
    public int takeAttendance5(int[] A) {
        //
        int left = 0;
        int right = A.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == mid) {
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        //判断一下是否是特殊情况：
        if(right == A[right]){
            return right + 1;
        }
        return right;
    }
    public int takeAttendance1(int[] records) {
        //
        //特殊情况处理
        int len = records.length;
        if(records[len - 1] == len - 1){
            return len ;
        }
        if(records[0] != 0){
            return 0;
        }
        //如何判断这一组有缺失——这个是要点
        int left = 0;
        int right = records.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;//注意：据情况修改这里的逻辑
            int real_count = mid - left + 1;
            int should_count = records[mid] - records[left] + 1;
            if (real_count < should_count) {

                right = mid ;
                if(right - left == 1){
                    return records[mid]-1;
                }
            }else{
                left = mid;
                if(right - left == 1){
                    return records[mid]+1;
                }
            }
        }
        //最后，要明确，left = right时，他俩指向的是啥？？？
        //实际模拟之后，发现是——缺失的后一个，也就是：比缺失项大1
        return records[left] - 1;

    }
}
